{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #库存管理 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #divide-and-conquer #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #分治 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: inventoryManagement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #库存管理 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>仓库管理员以数组 <code>stock</code> 形式记录商品库存表。<code>stock[i]</code> 表示商品 <code>id</code>，可能存在重复。请返回库存表中数量大于 <code>stock.length / 2</code> 的商品 <code>id</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>stock = [6, 1, 3, 1, 1, 1]\n",
    "<strong>输出: </strong>1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stock.length &lt;= 50000</code></li>\n",
    "\t<li>给定数组为非空数组，且存在结果数字</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>注意：本题与主站 169 题相同：<a href=\"https://leetcode-cn.com/problems/majority-element/\">https://leetcode-cn.com/problems/majority-element/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof](https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, nums: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in nums:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        res = None\n",
    "        cnt = 0\n",
    "        for num in stock:\n",
    "            if res == None or cnt == 0:\n",
    "                cnt = 1\n",
    "                res = num\n",
    "            elif res == num:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock.sort()\n",
    "        return stock[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        ans = stock[0]\n",
    "        hash = dict()\n",
    "        for num in stock:\n",
    "            hash[num] = hash.get(num, 0) + 1\n",
    "        for key, value in hash.items():\n",
    "            if value > len(stock) / 2:\n",
    "                ans = key\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x\n",
    "\n",
    "        # n = len(stock)\n",
    "        # hs = collections.defaultdict(int)\n",
    "        # for num in stock:\n",
    "        #     hs[num] += 1\n",
    "        #     nt = hs.get(num, -1)\n",
    "        #     if nt > n / 2: return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n = len(stock)\n",
    "        if n == 1:return stock[0] \n",
    "        for i in range(n):\n",
    "            if stock[i] in dic:\n",
    "                dic[stock[i]] += 1\n",
    "                if dic[stock[i]] > n / 2:return stock[i]\n",
    "            else:dic[stock[i]] = 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        # Counter\n",
    "        # C = collections.Counter(stock)\n",
    "        # print(C)\n",
    "        # n = len(stock)//2\n",
    "        # res = []\n",
    "        # for k, v in C.items():\n",
    "        #     if v > n:\n",
    "        #         return k\n",
    "        \n",
    "\n",
    "        # 官解\n",
    "        # if len(stock) == 1:\n",
    "        #     return stock[0]       \n",
    "        # stock.sort()\n",
    "        # return stock[len(stock)//2]\n",
    "\n",
    "\n",
    "        # 摩尔投票法\n",
    "        v = 0\n",
    "        for nu in stock:\n",
    "            if v == 0:\n",
    "                x = nu\n",
    "            v += 1 if nu == x else -1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x\n",
    "\n",
    "\n",
    "                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        \n",
    "        for i in stock:\n",
    "            if cnt==0:\n",
    "                cur = i\n",
    "                cnt = 1\n",
    "            elif i==cur:\n",
    "                cnt += 1\n",
    "            elif i!=cur:\n",
    "                cnt -= 1\n",
    "        \n",
    "        return cur\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dict1 = {}\n",
    "        n = len(stock)\n",
    "        res = []\n",
    "        for i in range(len(stock)):\n",
    "            if stock[i] not in list(dict1.keys()):\n",
    "                dict1[stock[i]] = 1\n",
    "            else:\n",
    "                dict1[stock[i]] += 1\n",
    "        for key, value in dict1.items():\n",
    "            if value > n/2:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic={}\n",
    "        for x in stock:\n",
    "            dic[x]=dic.get(x,0)+1\n",
    "        for key,value in dic.items():\n",
    "            if value>len(stock)/2:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock.sort()\n",
    "        return stock[int(len(stock)/2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, nums: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in nums:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, nums: List[int]) -> int:\n",
    "        major=0\n",
    "        count=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if count==0:\n",
    "                major=nums[i]\n",
    "            if nums[i]==major:\n",
    "                count+=1\n",
    "            else:\n",
    "                count-=1\n",
    "        if count:\n",
    "            return major"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        length = len(stock)/2\n",
    "        dict ={}\n",
    "        for i in stock:\n",
    "            dict[i] = 0 \n",
    "        for i in stock:\n",
    "            dict[i] = dict[i] + 1\n",
    "            if dict[i]>length:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        cnt = Counter(stock)\n",
    "        bd = len(stock) >> 1\n",
    "        for key in cnt:\n",
    "            if cnt[key] > bd:\n",
    "                return key\n",
    "        return 114514\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic, res = {}, float('inf')\n",
    "        for i in stock:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "            dic['t'] = dic.get('t', 0) + 0.5\n",
    "            if dic[i] > dic['t']:\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        datadict = {}\n",
    "        for i in range(len(stock)):\n",
    "            if stock[i] in datadict:\n",
    "                datadict[stock[i]] += 1\n",
    "            else:\n",
    "                datadict[stock[i]] = 1\n",
    "        num = len(stock) // 2\n",
    "        for key,value in datadict.items():\n",
    "            if value > num:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, nums: List[int]) -> int:\n",
    "        vote = 0\n",
    "        for num in nums:\n",
    "            if vote == 0:x = num\n",
    "            if x == num:\n",
    "                vote+=1\n",
    "            else:\n",
    "                vote-=1\n",
    "        return x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        tmp={}\n",
    "        for num in stock:\n",
    "            if not num in tmp:\n",
    "                tmp[num]=1\n",
    "            else:tmp[num]+=1\n",
    "        return max(tmp,key=tmp.get)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        rating = 1\n",
    "        res = stock[0]\n",
    "        for i in range(1, len(stock)):\n",
    "            if rating == 0:\n",
    "                res = stock[i]\n",
    "            if res == stock[i]:\n",
    "                rating += 1\n",
    "            else:\n",
    "                rating -= 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        a = 0\n",
    "        max_num = 0\n",
    "        for i in list(set(stock)):\n",
    "            if stock.count(i) > a:\n",
    "                a = stock.count(i)\n",
    "                max_num = i\n",
    "        \n",
    "        if a > len(stock)//2:\n",
    "            return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        threshold = len(stock)/2\n",
    "        table = {}\n",
    "        for i in stock:\n",
    "            if i in table.keys():\n",
    "                table[i] += 1\n",
    "            else:\n",
    "                table[i] = 1\n",
    "        \n",
    "        for i in table.keys():\n",
    "            if table[i] > threshold:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        # 统计\n",
    "        dic = Counter(stock)\n",
    "        for k,v in dic.items():\n",
    "            if v > len(stock)//2:\n",
    "                return k\n",
    "\n",
    "        # 数论 中位数 <-> 众数\n",
    "        return sorted(stock)[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in stock:\n",
    "            # print(i)\n",
    "            if i in dic:\n",
    "                # print(i)\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "\n",
    "            if dic[i]>len(stock)/2:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes=0\n",
    "        x = 0\n",
    "        for n in stock: \n",
    "            if votes == 0: x = n\n",
    "            votes += 1 if x == n else -1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        # if len(stock) == 1:\n",
    "        #     return stock[0]\n",
    "        stock.sort()\n",
    "        mid = len(stock) // 2\n",
    "\n",
    "        return stock[mid]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = len(stock)//2\n",
    "        count = Counter(stock)\n",
    "        for x in count:\n",
    "            if count[x] > n:\n",
    "                return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        cnt, ma = Counter(stock), len(stock) >> 1\n",
    "        for k, v in cnt.items():\n",
    "            if v > ma: return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        vote = 0\n",
    "        x = stock[0]\n",
    "        for num in stock:\n",
    "            if vote == 0:\n",
    "                x = num\n",
    "            if num == x:\n",
    "                vote += 1\n",
    "            else:\n",
    "                vote -= 1\n",
    "        return x\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        d =defaultdict(int)\n",
    "\n",
    "        for item in stock:\n",
    "            d[item] += 1 \n",
    "        \n",
    "        sorted_d = sorted(d.items(),key=lambda x:x[1])\n",
    "\n",
    "        return sorted_d[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock_dic=Counter(stock)\n",
    "        n=len(stock)\n",
    "        for i in stock_dic:\n",
    "            if stock_dic[i] > n/2 :\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock.sort()\n",
    "        return stock[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        votes, index = 0,stock[0]\n",
    "        for num in stock:\n",
    "            if votes == 0: \n",
    "                index = num\n",
    "                votes += 1\n",
    "                continue\n",
    "            if num != index:\n",
    "                votes -= 1\n",
    "            else:\n",
    "                votes += 1\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = 0\n",
    "        res = 0 \n",
    "        for i in stock:\n",
    "            if n == 0:\n",
    "                res = i \n",
    "                n += 1\n",
    "            else:\n",
    "                if res != i:\n",
    "                    n -= 1 \n",
    "                else:\n",
    "                    n += 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = 0\n",
    "        res = 0 \n",
    "        for i in stock:\n",
    "            if n == 0:\n",
    "                res = i \n",
    "            n += 1 if res == i else -1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        return sorted(stock)[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = len(stock)\n",
    "        half = n // 2\n",
    "        stock_map = {}\n",
    "        for s in stock:\n",
    "            stock_map[s] = stock_map.get(s, 0) + 1\n",
    "            if stock_map[s] > half:\n",
    "                return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        count = {}\n",
    "        for s in stock:\n",
    "            if s not in count:\n",
    "                count[s] = 1\n",
    "            else:\n",
    "                count[s] += 1\n",
    "            if count[s] > len(stock)/2:\n",
    "                return s\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        count = {}\n",
    "        for item in stock:\n",
    "            if item in count:\n",
    "                count[item] += 1\n",
    "            else:\n",
    "                count[item] = 1\n",
    "\n",
    "        for key, value in count.items():\n",
    "            if value > len(stock) / 2:\n",
    "                return key\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = len(stock)//2\n",
    "        count = Counter(stock)\n",
    "        for x in count:\n",
    "            if count[x] > n:\n",
    "                return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, nums: List[int]) -> int:\n",
    "        return collections.Counter(nums).most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic = {}\n",
    "        length = len(stock)/2\n",
    "        for i in stock:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        for key, value in dic.items():\n",
    "            if value > length:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        # stock.sort()\n",
    "        # return stock[len(stock) // 2]\n",
    "\n",
    "\n",
    "        count = 0\n",
    "        for num in stock:\n",
    "            if count == 0:\n",
    "                candidate = num\n",
    "            count += 1 if candidate == num else -1\n",
    "        return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        n = len(stock)//2\n",
    "        count = Counter(stock)\n",
    "        for x in count:\n",
    "            if count[x] > n:\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        #元素计数 求众数\n",
    "        a = collections.Counter(stock)\n",
    "        return max(a.keys(), key = a.get)\n",
    "\n",
    "        #摩尔投票 求众数\n",
    "        votes = 0\n",
    "        for num in stock:\n",
    "            if votes == 0: x = num\n",
    "            votes += 1 if num == x else -1\n",
    "        return x\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        count = 0\n",
    "        for num in stock:\n",
    "            if count == 0:\n",
    "                major = num\n",
    "                count = 1\n",
    "            elif major == num:\n",
    "                count += 1\n",
    "            else: count -= 1\n",
    "        return major"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        sum=0\n",
    "        for i in stock:\n",
    "           if sum==0:\n",
    "               head=i\n",
    "               sum=1 \n",
    "           else:\n",
    "                if head==i:\n",
    "                    sum+=1\n",
    "                else:\n",
    "                    sum-=1 \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock.sort()\n",
    "        return stock[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic={}\n",
    "        for num in stock:\n",
    "            if num in dic:\n",
    "                dic[num]+=1\n",
    "            else:\n",
    "                dic[num]=1\n",
    "        for i in dic:\n",
    "            if dic[i]>len(stock)/2:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        val,times = 0,0\n",
    "        for e in stock:\n",
    "            if times == 0:\n",
    "                val = e\n",
    "                times = 1\n",
    "                continue\n",
    "            if val != e:\n",
    "                times = times-1\n",
    "            else:\n",
    "                times = times+1\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        dic, res = {}, []\n",
    "        for i in stock:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        for key in dic:\n",
    "            if dic[key] > len(stock)/2:\n",
    "                return key\n",
    "        return null"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        \n",
    "        hash={}\n",
    "        for i in range(len(stock)):\n",
    "            if stock[i] in hash:\n",
    "                hash[stock[i]]+=1\n",
    "                if hash[stock[i]]>len(stock)/2:\n",
    "                    return stock[i]\n",
    "            else:\n",
    "                hash[stock[i]]=1\n",
    "        if len(stock)==1:\n",
    "            return stock[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        a,m={},stock[0]\n",
    "        for i in stock:\n",
    "            a[i]=a.get(i,0)+1\n",
    "        for i,j in a.items():\n",
    "            if j>a[m]:\n",
    "                m=i\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        count = collections.Counter(stock)\n",
    "        for key, val in count.items():\n",
    "            if val > len(stock) // 2:\n",
    "                return key\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        stock =  sorted(stock)\n",
    "        return stock[len(stock)//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        a,b = 'a', 0\n",
    "        for s in stock:\n",
    "            if b == 0:\n",
    "                a, b = s, 1\n",
    "            elif s==a:\n",
    "                b += 1\n",
    "            else:\n",
    "                b -= 1\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def inventoryManagement(self, stock: List[int]) -> int:\n",
    "        major = 0\n",
    "        count = 0\n",
    "        for num in stock:\n",
    "            if count == 0:\n",
    "                major = num\n",
    "                count = 1\n",
    "            elif major == num:\n",
    "                count += 1\n",
    "            else: count -= 1\n",
    "        return major"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
